//给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。 
//
// 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。 
//
// 
//
// 示例 1： 
// 
// 
//输入：nums = [-10,-3,0,5,9]
//输出：[0,-3,9,-10,null,5]
//解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
//
// 
//
// 示例 2： 
// 
// 
//输入：nums = [1,3]
//输出：[3,1]
//解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 10⁴ 
// -10⁴ <= nums[i] <= 10⁴ 
// nums 按 严格递增 顺序排列 
// 
//
// Related Topics 树 二叉搜索树 数组 分治 二叉树 👍 1268 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return  dfs(nums,0,nums.length-1);
    }

    public TreeNode dfs(int[] nums,int left,int right){
        if(left>right) return null;
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=dfs(nums,left,mid-1);
        root.right=dfs(nums,mid+1,right);
        return root;
    }



//    class AVLTree{
//        private  int val;
//        AVLTree left;
//        AVLTree right;
//
//        private  int height;
//
//        public AVLTree(int val) {
//            this.val = val;
//        }
//
//        public  int height(AVLTree node){
//            return node==null?0:node.height;
//        }
//
//        public void getHeight(AVLTree node){
//            node.height=Math.max(height(node.left),node.height(node.right))+1;
//        }
//
//        public int bf(AVLTree node){
//            return node.left.height-node.right.height;
//        }
//
//        public AVLTree leftRotate(AVLTree node){
//            AVLTree yellow=node.left;
//            AVLTree green=yellow.right;
//            node.left=green;
//            yellow.right=node;
//            return yellow;
//        }
//
//        public AVLTree rightleftRotate(AVLTree node){
//            node.left=rightRotate(node.left);
//            return leftRotate(node);
//        }
//
//        public AVLTree rightRotate(AVLTree node){
//            AVLTree yellow=node.right;
//            AVLTree green=yellow.left;
//            node.right=green;
//            yellow.left=node;
//            return yellow;
//        }
//
//        public AVLTree leftrightRotate(AVLTree node){
//            node.right=leftRotate(node.right);
//            return rightRotate(node);
//        }
//
//        public AVLTree balance(AVLTree node){
//            if(node==null){
//                return null;
//            }
//
//            if(bf(node)>1&&bf(node.left)>=0){
//               node= leftRotate(node);
//                return balance(node);
//            } else if (bf(node)<-1&&bf(node.right)<-1) {
//              node=  rightRotate(node);
//            } else if (bf(node)>1) {
//                node=rightleftRotate(node);
//                return  balance(node);
//            } else if (bf(node)<-1) {
//               node= leftrightRotate(node);
//               return balance(node);
//            }
//            return node;
//        }
//
//        public AVLTree add(AVLTree node,int offered){
//            if(node==null){
//                return new AVLTree(offered);
//            }
//
//            if(node.val<offered){
//                node.right=add(node.right,offered);
//
//            }
//            if(node.val>offered){
//                add(node.left,offered);
//
//            }
//
//            getHeight(node);
//           return balance(node);
//
//        }


//    }

}
//leetcode submit region end(Prohibit modification and deletion)
